Fisher-Yates Shuffle

18 April 2025
algorithm

The Fisher-Yates Shuffle was first described in 1938, by Ronald Fisher & Frank Yates. It is currently the gold standard for randomizing the elements of a sequential data structure & is most commonly associated with shuffling an array. It works by taking advantage of properties of the binomial co-efficient, in a way that shows both beauty & simplicity.

Complexity

Time: O(n)
Space: O(1)

Applications

Randomizing element order of a finite sequence (e.g. array)
Can be adapted to work with any linear data structure (e.g. linked list)

Limitations

Fails with non-linear data structures (e.g. graphs) because their elements do not for a sequence

Implementation

Prework

Data should be sequential (e.g. an array).

Steps

Given a 1-based array, loop from the highest to the lowest index
~Loop Starts~
1. Let n be the current index
2. Generate a random number between 1 & n inclusive
3. Swap the element at the current index, with the element at index of random number
. ~Loop Ends~
Return Array

Example - JavaScript

The below example is for randomizing the order of elements in a (0-based) JavaScript array.

function fisherYatesShuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        // Generate a random index between 0 and i
        const j = Math.floor(Math.random() * (i + 1));

        // Swap elements array[i] and array[j]
        [array[i], array[j]] = [array[j], array[i]];
    }
    return array;
}

// Usage:
const arr = [1, 2, 3, 4, 5];
const shuffledArr = fisherYatesShuffle(arr);
console.log(shuffledArr);

Practice Problem

LeetCode 384: Shuffle an Array